package org.agile4j.math.recursion;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author hanyx
 * @date 2019/01/04
 */
public class MergeSortDemo {

    /**
     * 使用递归实现 归并排序
     *
     * @param toSortArray 要排序的数组
     * @return
     */
    public static int[] mergeSort(int[] toSortArray) {
        if (toSortArray == null) {
            return new int[0];
        }

        // 如果分解到只剩一个数,返回该数
        if (toSortArray.length == 1) {
            return toSortArray;
        }

        // 将数组分解成左右两半
        int mid = toSortArray.length / 2;
        int[] left = Arrays.copyOfRange(toSortArray, 0, mid);
        int[] right = Arrays.copyOfRange(toSortArray, mid, toSortArray.length);

        // 嵌套调用,对两半分别进行排序
        left = mergeSort(left);
        right = mergeSort(right);

        // 合并排序后的两半
        int[] mergeArray = merge(left, right);
//        System.out.println(mergeArray);
        for (int a : mergeArray) {
            System.out.print(a + "\t");
        }
        System.out.println();
        return mergeArray;
    }

    /**
     * 合并2个已经排序完毕的数组
     *
     * @param a 第一个数组
     * @param b 第二个数组
     * @return int[] 合并后的数组
     */
    public static int[] merge(int[] a, int[] b) {

        if (a == null) {
            a = new int[0];
        }
        if (b == null) {
            b = new int[0];
        }

        int[] mergeArray = new int[a.length + b.length];

        int mi = 0, ai = 0, bi = 0;
        // 轮流从两个数组中取出较小的值,放入合并后的数组中
        while (ai < a.length && bi < b.length) {
            if (a[ai] < b[bi]) {
                mergeArray[mi] = a[ai];
                ai++;
            } else {
                mergeArray[mi] = b[bi];
                bi++;
            }
            mi++;
        }

        // 将某个数组内剩余的数字放入合并后的数组中
        if (ai < a.length) {
            for (int i = ai; i < a.length; i++) {
                mergeArray[mi] = a[i];
                mi++;
            }
        } else {
            for (int i = bi; i < b.length; i++) {
                mergeArray[mi] = b[i];
                mi++;
            }
        }
        return mergeArray;
    }

    public static void main(String[] args) {
        int[] toSort = {7, 6, 2, 4, 1, 9, 3, 8, 0, 5,10};
        int[] sortedArray = mergeSort(toSort);

        for (int a : sortedArray) {
            System.out.print(a + "\t");
        }

    }
}
